//
//  XBshortestWay.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/23.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBshortestWay.h"

// Floyd-Warshall 算法 -- 可以用来计算任意两点间的最短路径
#define  M 99999
void FloydWarshall()
{
    int way[4][4] = { //表示无向图的矩阵
        {0,2,6,4},
        {M,0,3,M},
        {7,M,0,1},
        {5,M,12,0},
    };
    //求任意两点之间的最短距离
    
    //way[i][j] 表示的是i到j的距离
    
   // way[i][k]=way[i][j]+way[j][k] 表示通过j点中转了
    int n =4 ;// n表示地点的数目
    // 求1 -2的最短距离
//    //for (int i =0; i<n; i++) {
//        
//        for (int j=0; j<n; j++) {
//            
//            if (way[1][2]>way[1][j]+way[j][2]) {
//                
//                way[1][2]=way[1][j]+way[j][2];//替换
//            }
//        }
    
    //}
    
//    //这里表示仅仅允许经过1号点中转。
//    for (int i =0; i<n; i++) {
//    
//        for (int j=0; j<n; j++) {
//            
//            if (way[i][j]>way[i][1]+way[1][j]) {
//                
//                way[i][j]=way[i][1]+way[1][j];//替换
//            }
//        }
//    
//    }
    
    
    // 可以通过任意顶点中转,经过i节点
    
        for (int i =0; i<n; i++) {
            for (int j=0; j<n; j++) {
                for (int k = 0; k< n;k++) {
                    
                    if (way[j][k]>way[j][i]+way[i][k]) {
                        
                        way[j][k]=way[j][i]+way[i][k];//替换
                    }
                }
            }
        }
}


// -- Dijkstra 算法 迪杰斯特拉算法 ，求单源最短路径，求一个点到其余各个点的最短路径
/*
 
 1.将所有的顶点分成两部分：已知最短路径的集合P和未知最短路径的顶点的集合Q，最开始最短路径的顶点集合P只有源点，需要区别顶点在哪个集合中
 2.设置源点s到自己的最短路径为0,若存在有源点能直接到达的顶点i则把dis[i],设置为e[s][i].同时把其他不能直接到达的源点设置为正无穷
 3.在集合Q中选择一个距离源点s最近的点u，放入集合P，并且对u进行松弛。
 4.重复第三步直到集合Q为空
 
 
 */


void Dijkstra()
{
        int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,min;
        int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
        //读入n和m，n表示顶点个数，m表示边的条数
        scanf("%d %d",&n,&m);
        
        //初始化
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j) e[i][j]=0;
                else e[i][j]=inf;
        
        //读入边
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&t1,&t2,&t3);
            e[t1][t2]=t3;
        }
        
        //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
        for(i=1;i<=n;i++)
            dis[i]=e[1][i];
        
        //book数组初始化
        for(i=1;i<=n;i++)
            book[i]=0;
        book[1]=1;//将源点加入P，
    
    int u=1;
    
    min = inf;
    for (int i =1; i<=n; i++) {//Q集合一共有n-1个点
        
        for (int k = 1; k<=n; k++) {//顶点的数目
            
            if (book[k]==0&&dis[k]<min) { //从dis数组中取数据，自己从e[1][k]中取了，错误了
                u=k;
            }
        }
        book[u]=1;
        for (int j=1; j<=n; j++) {//这也是顶点的数目
            
            if (dis[j]>dis[u]+e[u][j]) {
                
                dis[j]= dis[u]+e[u][j];
            }
        }
    
    }
        //输出最终的结果
    for(i=1;i<=n;i++)
        printf("%d ",dis[i]);
}
// -- 矩阵的存储可以使用邻接表优化



//----------------------------- Bellman-Ford 解决负边权问题,还可以用队列优化，以后写

void BellMAN()
{
    int dis[10],n,m,u[10],v[10],w[10],check,flag;
    int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d %d",&n,&m);
    
    //读入边
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&u[i],&v[i],&w[i]);//这里没有用二维矩阵存储，节省了空间
    }
    for (int i=2; i<=m; i++) { //1号顶点到其他点的距离
        
        dis[i] = inf;
    }
    dis[1]=0;
    
    for (int k=1; k<=n-1; k++) {// 顶点的数目，除去了源点自身
        check = 0;
        for (int i=1; i<=m; i++) {//边的个数 最多 n*（n-1)/2个边，效率不一定有迪杰斯特拉算法效率高
            
            if (dis[v[i]]>dis[u[i]]+w[i]) {// 根据边进行松弛
                
                dis[v[i]]=dis[u[i]]+w[i];
                check = 1;
            }
            if (check == 0) {
                
                break;
            }
        }
    }
    flag = 0;
    for (int i=1; i<=m; i++) {
        
        if (dis[v[i]]>dis[u[i]]+w[i]) {
            
            flag =1;
        }
    }
    //flag =1表示有负权值回路
    
}















































